package 并查集;
import java.util.Arrays;

/**
 * 并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。
 * 比如说，我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。
 * find()找到x的根节点
 * unite()将x和y的根节点合并
 * connected()判断x和y是不是同一分支
 * branchCount()有多少分支
 */
public class Solution {

    // 开启了路径压缩和按秩合并的并查集
    public class UnionFind {
        int[] parent;
        int[] size;
        // 当前连通分支数目
        int branchCount;
        public UnionFind(int n) {
            this.branchCount = n;
            this.parent = new int[n];
            this.size = new int[n];
            Arrays.fill(size, 1);
            for (int i = 0; i < n; ++i) {
                parent[i] = i;
            }
        }
        public int find(int x) {
            // 路径压缩
            return parent[x] == x ? x : (parent[x] = find(parent[x]));
        }
        public boolean unite(int x, int y) {
            x = find(x);
            y = find(y);
            if (x == y) {
                return false;
            }
            // 按秩合并
            if (size[x] < size[y]) {
                int temp = x;
                x = y;
                y = temp;
            }
            parent[y] = x;
            size[x] += size[y];
            --branchCount;
            return true;
        }
        public boolean connected(int x, int y) {
            return find(x) == find(y);
        }
        public int branchCount() {
            return branchCount;
        }
    }

}
